

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Nonlinear Convex Optimization &mdash; CVXOPT User&#39;s Guide</title>
  

  
  
  
  

  
  <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
        <script src="_static/jquery.js"></script>
        <script src="_static/underscore.js"></script>
        <script src="_static/doctools.js"></script>
        <script src="_static/language_data.js"></script>
    
    <script type="text/javascript" src="_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="copyright" title="Copyright" href="copyright.html" />
    <link rel="next" title="Modeling" href="modeling.html" />
    <link rel="prev" title="Cone Programming" href="coneprog.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="index.html" class="icon icon-home"> CVXOPT User's Guide
          

          
          </a>

          
            
            
              <div class="version">
                1.2.5
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <ul class="current">
<li class="toctree-l1"><a class="reference internal" href="copyright.html">Copyright and License</a></li>
<li class="toctree-l1"><a class="reference internal" href="intro.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="matrices.html">Dense and Sparse Matrices</a></li>
<li class="toctree-l1"><a class="reference internal" href="blas.html">The BLAS Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="lapack.html">The LAPACK Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="fftw.html">Discrete Transforms</a></li>
<li class="toctree-l1"><a class="reference internal" href="spsolvers.html">Sparse Linear Equations</a></li>
<li class="toctree-l1"><a class="reference internal" href="coneprog.html">Cone Programming</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Nonlinear Convex Optimization</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#problems-with-nonlinear-objectives">Problems with Nonlinear Objectives</a></li>
<li class="toctree-l2"><a class="reference internal" href="#problems-with-linear-objectives">Problems with Linear Objectives</a></li>
<li class="toctree-l2"><a class="reference internal" href="#geometric-programming">Geometric Programming</a></li>
<li class="toctree-l2"><a class="reference internal" href="#exploiting-structure">Exploiting Structure</a></li>
<li class="toctree-l2"><a class="reference internal" href="#algorithm-parameters">Algorithm Parameters</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="modeling.html">Modeling</a></li>
<li class="toctree-l1"><a class="reference internal" href="c-api.html">C API</a></li>
<li class="toctree-l1"><a class="reference internal" href="printing.html">Matrix Formatting</a></li>
<li class="toctree-l1"><a class="reference external" href="http://cvxopt.org">cvxopt.org</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="index.html">CVXOPT User's Guide</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="index.html">Docs</a> &raquo;</li>
        
      <li>Nonlinear Convex Optimization</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="nonlinear-convex-optimization">
<span id="c-solvers"></span><h1>Nonlinear Convex Optimization<a class="headerlink" href="#nonlinear-convex-optimization" title="Permalink to this headline">¶</a></h1>
<p>In this chapter we consider nonlinear convex optimization problems of the
form</p>
<div class="math">
<p><img src="_images/math/4e3f3707720cdc0ad65a45a1568034b0499846a9.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; f_0(x) \\
\mbox{subject to} &amp; f_k(x) \leq 0, \quad k=1,\ldots,m \\
                  &amp; G x \preceq h  \\
                  &amp; A x = b.
\end{array}"/></p>
</div><p>The functions <img class="math" src="_images/math/0edac3a6b0973196c5005c560d87e755c0ea5c86.png" alt="f_k"/> are convex and twice differentiable and the
linear inequalities are generalized inequalities with respect to a proper
convex cone, defined as a product of a nonnegative orthant, second-order
cones, and positive semidefinite cones.</p>
<p>The basic functions are <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a>, described in the sections
<a class="reference internal" href="#s-cp"><span class="std std-ref">Problems with Nonlinear Objectives</span></a> and <a class="reference internal" href="#s-cpl"><span class="std std-ref">Problems with Linear Objectives</span></a>.   A simpler interface for geometric
programming problems is discussed in the section <a class="reference internal" href="#s-gp"><span class="std std-ref">Geometric Programming</span></a>.
In the section <a class="reference internal" href="#s-nlcp"><span class="std std-ref">Exploiting Structure</span></a> we explain how custom solvers can be
implemented that exploit structure in specific classes of problems.
The last section
describes the algorithm parameters that control the solvers.</p>
<div class="section" id="problems-with-nonlinear-objectives">
<span id="s-cp"></span><h2>Problems with Nonlinear Objectives<a class="headerlink" href="#problems-with-nonlinear-objectives" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.solvers.cp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">cp</code><span class="sig-paren">(</span><em class="sig-param">F</em><span class="optional">[</span>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.cp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a convex optimization problem</p>
<div class="math" id="equation-e-nlcp">
<p><span class="eqno">(1)<a class="headerlink" href="#equation-e-nlcp" title="Permalink to this equation">¶</a></span><img src="_images/math/8d26408b917ad631b6ae90f7650b19b691fe2bb6.png" alt="\begin{array}{ll}
    \mbox{minimize}   &amp; f_0(x) \\
    \mbox{subject to} &amp; f_k(x) \leq 0, \quad k=1,\ldots,m \\
                      &amp; G x \preceq h  \\
                      &amp; A x = b.
\end{array}"/></p>
</div><p>The argument <code class="docutils literal notranslate"><span class="pre">F</span></code> is a function that evaluates the objective and
nonlinear constraint functions.  It must handle the following calling
sequences.</p>
<ul>
<li><p><code class="docutils literal notranslate"><span class="pre">F()</span></code> returns a tuple (<code class="docutils literal notranslate"><span class="pre">m</span></code>, <code class="docutils literal notranslate"><span class="pre">x0</span></code>), where <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> is
the number of nonlinear constraints and <img class="math" src="_images/math/ed7fb0260e58d3ca5851e823ff991dae4cde5671.png" alt="x_0"/> is a point in
the domain of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>.  <code class="docutils literal notranslate"><span class="pre">x0</span></code> is a dense real matrix of size
(<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1).</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">F(x)</span></code>, with <code class="docutils literal notranslate"><span class="pre">x</span></code> a dense real matrix of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1),
returns a tuple (<code class="docutils literal notranslate"><span class="pre">f</span></code>, <code class="docutils literal notranslate"><span class="pre">Df</span></code>).  <code class="docutils literal notranslate"><span class="pre">f</span></code> is a dense real matrix of
size (<img class="math" src="_images/math/4dc6347ee63e4c699378bbfd3c9c00e328e6a91d.png" alt="m+1"/>, 1), with <code class="docutils literal notranslate"><span class="pre">f[k]</span></code> equal to <img class="math" src="_images/math/b24f57eba06df79d80853a953d7805ab789ce829.png" alt="f_k(x)"/>.
(If <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> is zero, <code class="docutils literal notranslate"><span class="pre">f</span></code> can also be returned as a number.)
<code class="docutils literal notranslate"><span class="pre">Df</span></code> is a dense or sparse real matrix of size (<img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> + 1,
<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>) with <code class="docutils literal notranslate"><span class="pre">Df[k,:]</span></code> equal to the transpose of the
gradient <img class="math" src="_images/math/bc7ea4e9d78396e86d86c117f1b22f739b77aa10.png" alt="\nabla f_k(x)"/>.  If <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> is not in the domain
of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>, <code class="docutils literal notranslate"><span class="pre">F(x)</span></code> returns <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> or a tuple
(<code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>).</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">F(x,z)</span></code>, with <code class="docutils literal notranslate"><span class="pre">x</span></code> a dense real matrix of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1)
and <code class="docutils literal notranslate"><span class="pre">z</span></code> a positive dense real matrix of size (<img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> + 1, 1)
returns a tuple (<code class="docutils literal notranslate"><span class="pre">f</span></code>, <code class="docutils literal notranslate"><span class="pre">Df</span></code>, <code class="docutils literal notranslate"><span class="pre">H</span></code>).  <code class="docutils literal notranslate"><span class="pre">f</span></code> and <code class="docutils literal notranslate"><span class="pre">Df</span></code> are
defined as above.  <code class="docutils literal notranslate"><span class="pre">H</span></code> is a square dense or sparse real matrix of
size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>), whose lower triangular part contains
the lower triangular part of</p>
<div class="math">
<p><img src="_images/math/89d343471476626b56bc496f09d8fad108cb82a6.png" alt="z_0 \nabla^2f_0(x) + z_1 \nabla^2f_1(x) + \cdots +
    z_m \nabla^2f_m(x)."/></p>
</div><p>If <code class="docutils literal notranslate"><span class="pre">F</span></code> is called with two arguments, it can be assumed that
<img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> is in the domain of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>.</p>
</li>
</ul>
<p>The linear inequalities are with respect to a cone <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> defined
as a Cartesian product of a nonnegative orthant, a number of
second-order cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/03cfea18434ec87caa164206e463d7a230e1cb5c.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
    \cdots \times C_{M+N}"/></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/3725c3144c904e39aef17290ef9fdefa9e3adfe0.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
    C_0 &amp; =
        \{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\},\\
    C_{k+1} &amp; = \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1}
        \; | \; u_0 \geq \|u_1\|_2 \},  \quad k=0,\ldots, M-1, \\
    C_{k+M+1} &amp; = \left\{ \svec(u) \; | \; u \in \symm^{t_k}_+
        \right\}, \quad k=0,\ldots,N-1.
\end{split}"/></p>
</div><p>Here <img class="math" src="_images/math/5866199ac7f27f9fa8f345c8d6bd6f14fc869908.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix <img class="math" src="_images/math/9b444cf6329a14140aee8ff5a06ff30772cc1c2f.png" alt="u"/>
stored as a vector in column major order.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are real single-column dense matrices.
<code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are real dense or sparse matrices.  The default values
for <code class="docutils literal notranslate"><span class="pre">A</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are sparse matrices with zero rows, meaning that
there are no equality constraints.  The number of rows of <code class="docutils literal notranslate"><span class="pre">G</span></code> and
<code class="docutils literal notranslate"><span class="pre">h</span></code> is equal to</p>
<div class="math">
<p><img src="_images/math/95c7fad2a12f832a0675a00c80c4a8894297d2b8.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2."/></p>
</div><p>The columns of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> are vectors in</p>
<div class="math">
<p><img src="_images/math/1e0371cc3025278f588fd7d0ccfcc2510ff2f8cf.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2}  \times \cdots \times
\reals^{t_{N-1}^2},"/></p>
</div><p>where the last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> components represent symmetric matrices stored
in column major order.  The strictly upper triangular entries of these
matrices are not accessed (i.e., the symmetric matrices are stored
in the <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code>-type column major order used in the <code class="xref py py-mod docutils literal notranslate"><span class="pre">blas</span></code>
and <code class="xref py py-mod docutils literal notranslate"><span class="pre">lapack</span></code> modules).</p>
<p>The argument <code class="docutils literal notranslate"><span class="pre">dims</span></code> is a dictionary with the dimensions of the cones.
It has three fields.</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">dims['l']</span></code>:</dt><dd><p><img class="math" src="_images/math/470aa65888a2971c9346e573f12b37ea406b8ec9.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['q']</span></code>:</dt><dd><p><img class="math" src="_images/math/79b3736681052735beb52087fe8a1b6c188338fb.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['s']</span></code>:</dt><dd><p><img class="math" src="_images/math/d706fc3d557d35b283be36ac9e240324b68b34b9.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</p>
</dd>
</dl>
<p>The default value of <code class="docutils literal notranslate"><span class="pre">dims</span></code> is
<code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">h.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></code>, i.e., the default
assumption is that the linear inequalities are componentwise
inequalities.</p>
<p>The role of the optional argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> is explained in the
section <a class="reference internal" href="#s-nlcp"><span class="std std-ref">Exploiting Structure</span></a>.</p>
<p><a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> returns a dictionary that contains the result and
information about the accuracy of the solution.  The most important
fields have keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>.  The
possible values of the <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> key are:</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code></dt><dd><p>In this case the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> entry of the dictionary is the primal
optimal solution, the <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code> entries are
the corresponding slacks in the nonlinear and linear inequality
constraints, and the <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>
entries are the optimal values of the dual variables associated
with the nonlinear inequalities, the linear inequalities, and the
linear equality constraints.  These vectors approximately satisfy
the Karush-Kuhn-Tucker (KKT) conditions</p>
<div class="math">
<p><img src="_images/math/66e3f8da85954ae75f6016f5784d0ec468c2451c.png" alt="\nabla f_0(x) +  D\tilde f(x)^T z_\mathrm{nl} +
G^T z_\mathrm{l} + A^T y = 0,

\tilde f(x) + s_\mathrm{nl} = 0, \quad k=1,\ldots,m, \qquad
Gx + s_\mathrm{l} = h, \qquad Ax = b,

s_\mathrm{nl}\succeq 0, \qquad s_\mathrm{l}\succeq 0, \qquad
z_\mathrm{nl} \succeq 0, \qquad z_\mathrm{l} \succeq 0,

s_\mathrm{nl}^T z_\mathrm{nl} +
s_\mathrm{l}^T z_\mathrm{l} = 0"/></p>
</div><p>where <img class="math" src="_images/math/817f53603d7e46d0c89d94f741f3ff760e7b4e64.png" alt="\tilde f = (f_1,\ldots, f_m)"/>.</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code></dt><dd><p>This indicates that the algorithm terminated before a solution was
found, due to numerical difficulties or because the maximum number
of iterations was reached.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>
entries contain the iterates when the algorithm terminated.</p>
</dd>
</dl>
<p><a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> solves the problem by applying
<a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> to the epigraph
form problem</p>
<div class="math">
<p><img src="_images/math/5fa951f18d59f8caa1d2bc6ec81f6a0c945bfe75.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; t \\
\mbox{subject to} &amp; f_0(x) \leq t  \\
                  &amp; f_k(x) \leq 0, \quad k =1, \ldots, m \\
                  &amp; Gx \preceq h \\
                  &amp; Ax = b.
\end{array}"/></p>
</div><p>The other entries in the output dictionary of <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> describe
the accuracy of the solution and are copied from the output of
<a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> applied to this epigraph form
problem.</p>
<p><a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> requires that the problem is strictly primal and dual
feasible and that</p>
<div class="math">
<p><img src="_images/math/c72b037a60f8e81dc19add786e6d148794471f80.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank \left( \left[ \begin{array}{cccccc}
     \sum_{k=0}^m z_k \nabla^2 f_k(x) &amp; A^T &amp;
      \nabla f_1(x) &amp; \cdots \nabla f_m(x) &amp; G^T
      \end{array} \right] \right) = n,"/></p>
</div><p>for all <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and all positive <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>.</p>
</dd></dl>

<dl>
<dt><strong>Example: equality constrained analytic centering</strong></dt><dd><p>The equality constrained analytic centering problem is defined as</p>
<div class="math">
<p><img src="_images/math/ee3c949541ac51ceadec0a62713cdd8a42a2e4ab.png" alt="\begin{array}{ll}
\mbox{minimize} &amp; -\sum\limits_{i=1}^m \log x_i \\
\mbox{subject to} &amp; Ax = b.
\end{array}"/></p>
</div><p>The function <code class="xref py py-func docutils literal notranslate"><span class="pre">acent</span></code> defined  below solves the problem, assuming
it is solvable.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">log</span>

<span class="k">def</span> <span class="nf">acent</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">x</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">z</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">x</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span> <span class="k">return</span> <span class="mi">0</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
        <span class="k">if</span> <span class="nb">min</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="mf">0.0</span><span class="p">:</span> <span class="k">return</span> <span class="kc">None</span>
        <span class="n">f</span> <span class="o">=</span> <span class="o">-</span><span class="nb">sum</span><span class="p">(</span><span class="n">log</span><span class="p">(</span><span class="n">x</span><span class="p">))</span>
        <span class="n">Df</span> <span class="o">=</span> <span class="o">-</span><span class="p">(</span><span class="n">x</span><span class="o">**-</span><span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">T</span>
        <span class="k">if</span> <span class="n">z</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span> <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span>
        <span class="n">H</span> <span class="o">=</span> <span class="n">spdiag</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="n">x</span><span class="o">**-</span><span class="mi">2</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span><span class="p">,</span> <span class="n">H</span>
    <span class="k">return</span> <span class="n">solvers</span><span class="o">.</span><span class="n">cp</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="n">A</span><span class="o">=</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="o">=</span><span class="n">b</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span>
</pre></div>
</div>
</dd>
<dt><strong>Example: robust least-squares</strong></dt><dd><p>The function <code class="xref py py-func docutils literal notranslate"><span class="pre">robls</span></code> defined below solves the unconstrained
problem</p>
<div class="math">
<p><img src="_images/math/c0ff36623c1ad325126fbebd6724e58809c4fdd2.png" alt="\begin{array}{ll}
\mbox{minimize} &amp;  \sum\limits_{k=1}^m \phi((Ax-b)_k),
\end{array}
\qquad \phi(u) = \sqrt{\rho + u^2},"/></p>
</div><p>where <img class="math" src="_images/math/4357a4e29a351ac6ae90924cc00e06184fbd8412.png" alt="A \in\mathbf{R}^{m\times n}"/>.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">sqrt</span><span class="p">,</span> <span class="n">div</span>

<span class="k">def</span> <span class="nf">robls</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">rho</span><span class="p">):</span>
    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">x</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">z</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">x</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span> <span class="k">return</span> <span class="mi">0</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
        <span class="n">y</span> <span class="o">=</span> <span class="n">A</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">b</span>
        <span class="n">w</span> <span class="o">=</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">rho</span> <span class="o">+</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span>
        <span class="n">f</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">(</span><span class="n">w</span><span class="p">)</span>
        <span class="n">Df</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">w</span><span class="p">)</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">A</span>
        <span class="k">if</span> <span class="n">z</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span> <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span>
        <span class="n">H</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">spdiag</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="n">rho</span><span class="o">*</span><span class="p">(</span><span class="n">w</span><span class="o">**-</span><span class="mi">3</span><span class="p">))</span> <span class="o">*</span> <span class="n">A</span>
        <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span><span class="p">,</span> <span class="n">H</span>
    <span class="k">return</span> <span class="n">solvers</span><span class="o">.</span><span class="n">cp</span><span class="p">(</span><span class="n">F</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span>
</pre></div>
</div>
</dd>
</dl>
<p><strong>Example: analytic centering with cone constraints</strong></p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/fb07faac9fe824b206392c19b7a1a2c6dd70e1ee.png" alt="\begin{array}{ll}
\mbox{minimize}
    &amp; -\log(1-x_1^2) -\log(1-x_2^2) -\log(1-x_3^2) \\
\mbox{subject to}
    &amp; \|x\|_2 \leq 1 \\
    &amp; x_1 \left[\begin{array}{rrr}
          -21 &amp; -11 &amp; 0 \\ -11 &amp; 10 &amp; 8 \\ 0 &amp; 8 &amp; 5
           \end{array}\right] +
      x_2 \left[\begin{array}{rrr}
           0 &amp; 10 &amp; 16 \\ 10 &amp; -10 &amp; -10 \\ 16 &amp; -10 &amp; 3
          \end{array}\right] +
      x_3 \left[\begin{array}{rrr}
          -5 &amp; 2 &amp; -17 \\ 2 &amp; -6 &amp; 8 \\ -17 &amp; -7 &amp; 6
          \end{array}\right]
      \preceq \left[\begin{array}{rrr}
          20 &amp; 10 &amp; 40 \\ 10 &amp; 80 &amp; 10 \\ 40 &amp; 10 &amp; 15
          \end{array}\right].
\end{array}"/></p>
</div><div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">log</span><span class="p">,</span> <span class="n">div</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">solvers</span>

<span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">x</span> <span class="o">=</span> <span class="kc">None</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="kc">None</span><span class="p">):</span>
     <span class="k">if</span> <span class="n">x</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>  <span class="k">return</span> <span class="mi">0</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
     <span class="k">if</span> <span class="nb">max</span><span class="p">(</span><span class="nb">abs</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">&gt;=</span> <span class="mf">1.0</span><span class="p">:</span>  <span class="k">return</span> <span class="kc">None</span>
     <span class="n">u</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span>
     <span class="n">val</span> <span class="o">=</span> <span class="o">-</span><span class="nb">sum</span><span class="p">(</span><span class="n">log</span><span class="p">(</span><span class="n">u</span><span class="p">))</span>
     <span class="n">Df</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="n">u</span><span class="p">)</span><span class="o">.</span><span class="n">T</span>
     <span class="k">if</span> <span class="n">z</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>  <span class="k">return</span> <span class="n">val</span><span class="p">,</span> <span class="n">Df</span>
     <span class="n">H</span> <span class="o">=</span> <span class="n">spdiag</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="n">z</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="n">div</span><span class="p">(</span><span class="mi">1</span> <span class="o">+</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">u</span><span class="o">**</span><span class="mi">2</span><span class="p">))</span>
     <span class="k">return</span> <span class="n">val</span><span class="p">,</span> <span class="n">Df</span><span class="p">,</span> <span class="n">H</span>

<span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">21.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span>  <span class="mf">10.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">],</span>
             <span class="p">[</span><span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span>  <span class="mf">10.</span><span class="p">,</span>  <span class="mf">16.</span><span class="p">,</span>  <span class="mf">10.</span><span class="p">,</span> <span class="o">-</span><span class="mf">10.</span><span class="p">,</span> <span class="o">-</span><span class="mf">10.</span><span class="p">,</span>  <span class="mf">16.</span><span class="p">,</span> <span class="o">-</span><span class="mf">10.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">],</span>
             <span class="p">[</span><span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">5.</span><span class="p">,</span>   <span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">17.</span><span class="p">,</span>   <span class="mf">2.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">6.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span> <span class="o">-</span><span class="mf">17.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">7.</span><span class="p">,</span> <span class="mf">6.</span><span class="p">]</span> <span class="p">])</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">20.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">15.</span><span class="p">])</span>
<span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[</span><span class="mi">4</span><span class="p">],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span>  <span class="p">[</span><span class="mi">3</span><span class="p">]}</span>
<span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">cp</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">)</span>
<span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">])</span>
<span class="p">[</span> <span class="mf">4.11e-01</span><span class="p">]</span>
<span class="p">[</span> <span class="mf">5.59e-01</span><span class="p">]</span>
<span class="p">[</span><span class="o">-</span><span class="mf">7.20e-01</span><span class="p">]</span>
</pre></div>
</div>
</div></blockquote>
</div>
<div class="section" id="problems-with-linear-objectives">
<span id="s-cpl"></span><h2>Problems with Linear Objectives<a class="headerlink" href="#problems-with-linear-objectives" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.solvers.cpl">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">cpl</code><span class="sig-paren">(</span><em class="sig-param">c</em>, <em class="sig-param">F</em><span class="optional">[</span>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.cpl" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a convex optimization problem with a linear objective</p>
<div class="math">
<p><img src="_images/math/86cec286c2bbedaa7760445bc5a1a242cb84d2c2.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; c^T x \\
\mbox{subject to} &amp; f_k(x) \leq 0, \quad k=0,\ldots,m-1 \\
                  &amp; G x \preceq h  \\
                  &amp; A x = b.
\end{array}"/></p>
</div><p><code class="docutils literal notranslate"><span class="pre">c</span></code> is a real single-column dense matrix.</p>
<p><code class="docutils literal notranslate"><span class="pre">F</span></code> is a function that evaluates the nonlinear constraint functions.
It must handle the following calling sequences.</p>
<ul>
<li><p><code class="docutils literal notranslate"><span class="pre">F()</span></code> returns a tuple (<code class="docutils literal notranslate"><span class="pre">m</span></code>, <code class="docutils literal notranslate"><span class="pre">x0</span></code>), where <code class="docutils literal notranslate"><span class="pre">m</span></code> is the
number of nonlinear constraints and <code class="docutils literal notranslate"><span class="pre">x0</span></code> is a point in the domain
of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>.  <code class="docutils literal notranslate"><span class="pre">x0</span></code> is a dense real matrix of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1).</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">F(x)</span></code>, with <code class="docutils literal notranslate"><span class="pre">x</span></code> a dense real matrix of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1),
returns a tuple (<code class="docutils literal notranslate"><span class="pre">f</span></code>, <code class="docutils literal notranslate"><span class="pre">Df</span></code>).  <code class="docutils literal notranslate"><span class="pre">f</span></code> is a dense real matrix of
size (<img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/>, 1), with <code class="docutils literal notranslate"><span class="pre">f[k]</span></code> equal to <img class="math" src="_images/math/b24f57eba06df79d80853a953d7805ab789ce829.png" alt="f_k(x)"/>.
<code class="docutils literal notranslate"><span class="pre">Df</span></code> is a dense or sparse real matrix of size (<img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/>,
<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>) with <code class="docutils literal notranslate"><span class="pre">Df[k,:]</span></code> equal to the transpose of the
gradient <img class="math" src="_images/math/bc7ea4e9d78396e86d86c117f1b22f739b77aa10.png" alt="\nabla f_k(x)"/>.  If <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> is not in the domain
of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>, <code class="docutils literal notranslate"><span class="pre">F(x)</span></code> returns <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> or a tuple
(<code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>).</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">F(x,z)</span></code>, with <code class="docutils literal notranslate"><span class="pre">x</span></code> a dense real matrix of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1)
and <code class="docutils literal notranslate"><span class="pre">z</span></code> a positive dense real matrix of size (<img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/>, 1)
returns a tuple (<code class="docutils literal notranslate"><span class="pre">f</span></code>, <code class="docutils literal notranslate"><span class="pre">Df</span></code>, <code class="docutils literal notranslate"><span class="pre">H</span></code>).  <code class="docutils literal notranslate"><span class="pre">f</span></code> and <code class="docutils literal notranslate"><span class="pre">Df</span></code> are defined
as above.  <code class="docutils literal notranslate"><span class="pre">H</span></code> is a square dense or sparse real matrix of size
(<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>), whose lower triangular part contains the
lower triangular part of</p>
<div class="math">
<p><img src="_images/math/64824b782d63f742bca8b398e0f12b485771f257.png" alt="z_0 \nabla^2f_0(x) + z_1 \nabla^2f_1(x) + \cdots +
z_{m-1} \nabla^2f_{m-1}(x)."/></p>
</div><p>If <code class="docutils literal notranslate"><span class="pre">F</span></code> is called with two arguments, it can be assumed that
<img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> is in the domain of <img class="math" src="_images/math/5b7752c757e0b691a80ab8227eadb8a8389dc58a.png" alt="f"/>.</p>
</li>
</ul>
<p>The linear inequalities are with respect to a cone <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> defined as
a Cartesian product of a nonnegative orthant, a number of second-order
cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/facdb23d2bcdc9cf5d90ab695c86965ac188e3e5.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
\cdots \times C_{M+N}"/></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/0b6da08d6fc1f85c1382af2c64a51fa0129e47fd.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
C_0 &amp;= \{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\}, \\
C_{k+1} &amp;= \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1} \; | \;
    u_0 \geq \|u_1\|_2 \},  \quad k=0,\ldots, M-1, \\
C_{k+M+1} &amp;= \left\{ \svec(u) \; | \;
    u \in \symm^{t_k}_+ \right\}, \quad k=0,\ldots,N-1.
\end{split}"/></p>
</div><p>Here <img class="math" src="_images/math/5866199ac7f27f9fa8f345c8d6bd6f14fc869908.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix <img class="math" src="_images/math/9b444cf6329a14140aee8ff5a06ff30772cc1c2f.png" alt="u"/>
stored as a vector in column major order.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are real single-column dense matrices.
<code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are real dense or sparse matrices.  The default values
for <code class="docutils literal notranslate"><span class="pre">A</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are sparse matrices with zero rows, meaning that
there are no equality constraints.  The number of rows of <code class="docutils literal notranslate"><span class="pre">G</span></code> and
<code class="docutils literal notranslate"><span class="pre">h</span></code> is equal to</p>
<div class="math">
<p><img src="_images/math/95c7fad2a12f832a0675a00c80c4a8894297d2b8.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2."/></p>
</div><p>The columns of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> are vectors in</p>
<div class="math">
<p><img src="_images/math/1e0371cc3025278f588fd7d0ccfcc2510ff2f8cf.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2}  \times \cdots \times
\reals^{t_{N-1}^2},"/></p>
</div><p>where the last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> components represent symmetric matrices stored
in column major order.  The strictly upper triangular entries of these
matrices are not accessed (i.e., the symmetric matrices are stored
in the <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code>-type column major order used in the <code class="xref py py-mod docutils literal notranslate"><span class="pre">blas</span></code> and
<code class="xref py py-mod docutils literal notranslate"><span class="pre">lapack</span></code> modules.</p>
<p>The argument <code class="docutils literal notranslate"><span class="pre">dims</span></code> is a dictionary with the dimensions of the cones.
It has three fields.</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">dims['l']</span></code>:</dt><dd><p><img class="math" src="_images/math/470aa65888a2971c9346e573f12b37ea406b8ec9.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['q']</span></code>:</dt><dd><p><img class="math" src="_images/math/79b3736681052735beb52087fe8a1b6c188338fb.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['s']</span></code>:</dt><dd><p><img class="math" src="_images/math/d706fc3d557d35b283be36ac9e240324b68b34b9.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</p>
</dd>
</dl>
<p>The default value of <code class="docutils literal notranslate"><span class="pre">dims</span></code> is
<code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">h.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></code>, i.e., the default
assumption is that the linear inequalities are componentwise
inequalities.</p>
<p>The role of the optional argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> is explained in the
section <a class="reference internal" href="#s-nlcp"><span class="std std-ref">Exploiting Structure</span></a>.</p>
<p><a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> returns a dictionary that contains the result and
information about the accuracy of the solution.  The most important
fields have keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>.
The possible values of the <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> key are:</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code></dt><dd><p>In this case the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> entry of the dictionary is the primal
optimal solution, the <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code> entries are
the corresponding slacks in the nonlinear and linear inequality
constraints, and the <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>, and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> entries are the optimal values of the dual variables
associated with the nonlinear inequalities, the linear
inequalities, and the linear equality constraints.  These vectors
approximately satisfy the Karush-Kuhn-Tucker (KKT) conditions</p>
<div class="math">
<p><img src="_images/math/deb40d5eca48a271c62dc3937746712359cd3b05.png" alt="c +  Df(x)^T z_\mathrm{nl} + G^T z_\mathrm{l} + A^T y = 0,

f(x) + s_\mathrm{nl} = 0, \quad k=1,\ldots,m, \qquad
    Gx + s_\mathrm{l} = h, \qquad Ax = b,


s_\mathrm{nl}\succeq 0, \qquad s_\mathrm{l}\succeq 0, \qquad
    z_\mathrm{nl} \succeq 0, \qquad z_\mathrm{l} \succeq 0,

s_\mathrm{nl}^T z_\mathrm{nl} +  s_\mathrm{l}^T z_\mathrm{l}
    = 0."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code></dt><dd><p>This indicates that the algorithm terminated before a solution was
found, due to numerical difficulties or because the maximum number
of iterations was reached.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>
entries contain the iterates when the algorithm terminated.</p>
</dd>
</dl>
<p>The other entries in the output dictionary describe the accuracy
of the solution.  The entries <code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">objective'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">objective'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'gap'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'relative</span> <span class="pre">gap'</span></code>     give the primal objective <img class="math" src="_images/math/db7426d70cdd8a4c33c3f1b8f7bdc9ba1b62c43a.png" alt="c^Tx"/>, the dual objective, calculated
as</p>
<div class="math">
<p><img src="_images/math/95af1725828b1a188bbb0d933ffc78ef94788a48.png" alt="c^Tx + z_\mathrm{nl}^T f(x) + z_\mathrm{l}^T (Gx - h) + y^T(Ax-b),"/></p>
</div><p>the duality gap</p>
<div class="math">
<p><img src="_images/math/b0f4d6da17f2d5db3b4617e0e0d14eaf0b976b4b.png" alt="s_\mathrm{nl}^T z_\mathrm{nl} +  s_\mathrm{l}^T z_\mathrm{l},"/></p>
</div><p>and the relative gap.  The relative gap is defined as</p>
<div class="math">
<p><img src="_images/math/3a138e23ab33c536c23ad13ff28606737fe7e610.png" alt="\frac{\mbox{gap}}{-\mbox{primal objective}}
    \quad \mbox{if\ } \mbox{primal objective} &lt; 0, \qquad
\frac{\mbox{gap}}{\mbox{dual objective}}
    \quad \mbox{if\ } \mbox{dual objective} &gt; 0,"/></p>
</div><p>and <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> otherwise.  The entry with key
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></code> gives the residual in the primal
constraints,</p>
<div class="math">
<p><img src="_images/math/7627c2662a2a563bf350d8d618dd7e6d40c35e2e.png" alt="\newcommand{\ones}{{\bf 1}}
\frac{\| ( f(x) + s_{\mathrm{nl}},  Gx + s_\mathrm{l} - h,
    Ax-b ) \|_2} {\max\{1, \| ( f(x_0) + \ones,
Gx_0 + \ones-h, Ax_0-b) \|_2 \}}"/></p>
</div><p>where <img class="math" src="_images/math/ed7fb0260e58d3ca5851e823ff991dae4cde5671.png" alt="x_0"/> is the point returned by <code class="docutils literal notranslate"><span class="pre">F()</span></code>.  The entry
with key <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></code> gives the residual</p>
<div class="math">
<p><img src="_images/math/ccfd8c814cc1234e5dc5fce8871570757d15515c.png" alt="\newcommand{\ones}{{\bf 1}}
\frac
    { \| c +  Df(x)^Tz_\mathrm{nl} + G^Tz_\mathrm{l} + A^T y \|_2}
    { \max\{ 1, \| c + Df(x_0)^T\ones + G^T\ones \|_2 \} }."/></p>
</div><p><a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> requires that the problem is strictly primal and dual
feasible and that</p>
<div class="math">
<p><img src="_images/math/55eedb919b02b7a0654137bd319d8bb919ad3067.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank\left(\left[\begin{array}{cccccc}
    \sum_{k=0}^{m-1} z_k \nabla^2 f_k(x) &amp; A^T &amp;
    \nabla f_0(x) &amp; \cdots \nabla f_{m-1}(x) &amp; G^T
    \end{array}\right]\right) = n,"/></p>
</div><p>for all <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and all positive <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>.</p>
</dd></dl>

<dl>
<dt><strong>Example: floor planning</strong></dt><dd><p>This example is the floor planning problem of section 8.8.2 in the book
<a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex Optimization</a>:</p>
<div class="math">
<p><img src="_images/math/124ef7067b147c5c7f031fc0fc06a822029456c1.png" alt="\begin{array}{ll}
\mbox{minimize}    &amp; W + H \\
\mbox{subject to}
    &amp; A_{\mathrm{min}, k}/h_k - w_k \leq 0, \quad k=1,\ldots, 5 \\
    &amp; x_1 \geq 0, \quad x_2 \geq 0,  \quad x_4 \geq 0 \\
    &amp; x_1 + w_1 + \rho \leq x_3, \quad x_2 + w_2 + \rho \leq x_3,
      \quad x_3 + w_3 + \rho \leq x_5,  \\
    &amp; x_4 + w_4 + \rho \leq x_5, \quad x_5 + w_5 \leq W \\
    &amp; y_2 \geq 0,  \quad y_3 \geq 0, \quad y_5 \geq 0  \\
    &amp; y_2 + h_2 + \rho \leq y_1, \quad y_1 + h_1 + \rho \leq y_4,
      y_3 + h_3 + \rho \leq y_4, \\
    &amp; y_4 + h_4 \leq H, \quad y_5 + h_5 \leq H \\
    &amp; h_k/\gamma \leq w_k \leq \gamma h_k, \quad k=1,\ldots,5.
\end{array}"/></p>
</div><p>This problem has 22 variables</p>
<div class="math">
<p><img src="_images/math/0f2f6181474c4d231456601880211909048d0548.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
W, \qquad H, \qquad x\in\reals^5, \qquad y\in\reals^5, \qquad
w\in\reals^5, \qquad h\in\reals^5,"/></p>
</div><p>5 nonlinear inequality constraints, and 26 linear inequality
constraints.  The code belows defines a function <code class="xref py py-func docutils literal notranslate"><span class="pre">floorplan</span></code>
that solves the problem by calling <code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code>, then applies it to
4 instances, and creates a figure.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">pylab</span>
<span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spmatrix</span><span class="p">,</span> <span class="n">mul</span><span class="p">,</span> <span class="n">div</span>

<span class="k">def</span> <span class="nf">floorplan</span><span class="p">(</span><span class="n">Amin</span><span class="p">):</span>

    <span class="c1">#     minimize    W+H</span>
    <span class="c1">#     subject to  Amink / hk &lt;= wk, k = 1,..., 5</span>
    <span class="c1">#                 x1 &gt;= 0,  x2 &gt;= 0, x4 &gt;= 0</span>
    <span class="c1">#                 x1 + w1 + rho &lt;= x3</span>
    <span class="c1">#                 x2 + w2 + rho &lt;= x3</span>
    <span class="c1">#                 x3 + w3 + rho &lt;= x5</span>
    <span class="c1">#                 x4 + w4 + rho &lt;= x5</span>
    <span class="c1">#                 x5 + w5 &lt;= W</span>
    <span class="c1">#                 y2 &gt;= 0,  y3 &gt;= 0,  y5 &gt;= 0</span>
    <span class="c1">#                 y2 + h2 + rho &lt;= y1</span>
    <span class="c1">#                 y1 + h1 + rho &lt;= y4</span>
    <span class="c1">#                 y3 + h3 + rho &lt;= y4</span>
    <span class="c1">#                 y4 + h4 &lt;= H</span>
    <span class="c1">#                 y5 + h5 &lt;= H</span>
    <span class="c1">#                 hk/gamma &lt;= wk &lt;= gamma*hk,  k = 1, ..., 5</span>
    <span class="c1">#</span>
    <span class="c1"># 22 Variables W, H, x (5), y (5), w (5), h (5).</span>
    <span class="c1">#</span>
    <span class="c1"># W, H:  scalars; bounding box width and height</span>
    <span class="c1"># x, y:  5-vectors; coordinates of bottom left corners of blocks</span>
    <span class="c1"># w, h:  5-vectors; widths and heigths of the 5 blocks</span>

    <span class="n">rho</span><span class="p">,</span> <span class="n">gamma</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">5.0</span>   <span class="c1"># min spacing, min aspect ratio</span>

    <span class="c1"># The objective is to minimize W + H.  There are five nonlinear</span>
    <span class="c1"># constraints</span>
    <span class="c1">#</span>
    <span class="c1">#     -wk + Amink / hk &lt;= 0,  k = 1, ..., 5</span>

    <span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="p">[</span><span class="mf">1.0</span><span class="p">]</span> <span class="o">+</span> <span class="mi">20</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">])</span>

    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">x</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">z</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">x</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>  <span class="k">return</span> <span class="mi">5</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mi">17</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="mi">5</span><span class="o">*</span><span class="p">[</span><span class="mf">1.0</span><span class="p">])</span>
        <span class="k">if</span> <span class="nb">min</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="mi">17</span><span class="p">:])</span> <span class="o">&lt;=</span> <span class="mf">0.0</span><span class="p">:</span>  <span class="k">return</span> <span class="kc">None</span>
        <span class="n">f</span> <span class="o">=</span> <span class="o">-</span><span class="n">x</span><span class="p">[</span><span class="mi">12</span><span class="p">:</span><span class="mi">17</span><span class="p">]</span> <span class="o">+</span> <span class="n">div</span><span class="p">(</span><span class="n">Amin</span><span class="p">,</span> <span class="n">x</span><span class="p">[</span><span class="mi">17</span><span class="p">:])</span>
        <span class="n">Df</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">22</span><span class="p">))</span>
        <span class="n">Df</span><span class="p">[:,</span><span class="mi">12</span><span class="p">:</span><span class="mi">17</span><span class="p">]</span> <span class="o">=</span> <span class="n">spmatrix</span><span class="p">(</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">),</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">))</span>
        <span class="n">Df</span><span class="p">[:,</span><span class="mi">17</span><span class="p">:]</span> <span class="o">=</span> <span class="n">spmatrix</span><span class="p">(</span><span class="o">-</span><span class="n">div</span><span class="p">(</span><span class="n">Amin</span><span class="p">,</span> <span class="n">x</span><span class="p">[</span><span class="mi">17</span><span class="p">:]</span><span class="o">**</span><span class="mi">2</span><span class="p">),</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">),</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">))</span>
        <span class="k">if</span> <span class="n">z</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span> <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span>
        <span class="n">H</span> <span class="o">=</span> <span class="n">spmatrix</span><span class="p">(</span> <span class="mf">2.0</span><span class="o">*</span> <span class="n">mul</span><span class="p">(</span><span class="n">z</span><span class="p">,</span> <span class="n">div</span><span class="p">(</span><span class="n">Amin</span><span class="p">,</span> <span class="n">x</span><span class="p">[</span><span class="mi">17</span><span class="p">::]</span><span class="o">**</span><span class="mi">3</span><span class="p">)),</span> <span class="nb">range</span><span class="p">(</span><span class="mi">17</span><span class="p">,</span><span class="mi">22</span><span class="p">),</span> <span class="nb">range</span><span class="p">(</span><span class="mi">17</span><span class="p">,</span><span class="mi">22</span><span class="p">)</span> <span class="p">)</span>
        <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">Df</span><span class="p">,</span> <span class="n">H</span>

    <span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">26</span><span class="p">,</span><span class="mi">22</span><span class="p">))</span>
    <span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">26</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                       <span class="c1"># -x1 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                       <span class="c1"># -x2 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                       <span class="c1"># -x4 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">12</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>     <span class="c1"># x1 - x3 + w1 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">13</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>     <span class="c1"># x2 - x3 + w2 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">5</span><span class="p">,</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">14</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">5</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>     <span class="c1"># x3 - x5 + w3 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="p">[</span><span class="mi">5</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">15</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>     <span class="c1"># x4 - x5 + w4 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">7</span><span class="p">,</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">16</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span>                   <span class="c1"># -W + x5 + w5 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">8</span><span class="p">,</span><span class="mi">8</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                       <span class="c1"># -y2 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">9</span><span class="p">,</span><span class="mi">9</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                       <span class="c1"># -y3 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">10</span><span class="p">,</span><span class="mi">11</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>                                     <span class="c1"># -y5 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">11</span><span class="p">,</span> <span class="p">[</span><span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">18</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">11</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>   <span class="c1"># -y1 + y2 + h2 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">12</span><span class="p">,</span> <span class="p">[</span><span class="mi">7</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">17</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">12</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>  <span class="c1">#  y1 - y4 + h1 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">13</span><span class="p">,</span> <span class="p">[</span><span class="mi">9</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">19</span><span class="p">]],</span> <span class="n">h</span><span class="p">[</span><span class="mi">13</span><span class="p">]</span> <span class="o">=</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">],</span> <span class="o">-</span><span class="n">rho</span>  <span class="c1">#  y3 - y4 + h3 &lt;= -rho</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">14</span><span class="p">,</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">20</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span>                 <span class="c1"># -H + y4 + h4 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">15</span><span class="p">,</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="mi">21</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span>                 <span class="c1"># -H + y5 + h5 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">16</span><span class="p">,</span> <span class="p">[</span><span class="mi">12</span><span class="p">,</span> <span class="mi">17</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">gamma</span>                   <span class="c1"># -w1 + h1/gamma &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">17</span><span class="p">,</span> <span class="p">[</span><span class="mi">12</span><span class="p">,</span> <span class="mi">17</span><span class="p">]]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="n">gamma</span>                       <span class="c1">#  w1 - gamma * h1 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">18</span><span class="p">,</span> <span class="p">[</span><span class="mi">13</span><span class="p">,</span> <span class="mi">18</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">gamma</span>                   <span class="c1"># -w2 + h2/gamma &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">19</span><span class="p">,</span> <span class="p">[</span><span class="mi">13</span><span class="p">,</span> <span class="mi">18</span><span class="p">]]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="n">gamma</span>                       <span class="c1">#  w2 - gamma * h2 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">20</span><span class="p">,</span> <span class="p">[</span><span class="mi">14</span><span class="p">,</span> <span class="mi">19</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">gamma</span>                   <span class="c1"># -w3 + h3/gamma &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">21</span><span class="p">,</span> <span class="p">[</span><span class="mi">14</span><span class="p">,</span> <span class="mi">19</span><span class="p">]]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="n">gamma</span>                       <span class="c1">#  w3 - gamma * h3 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">22</span><span class="p">,</span> <span class="p">[</span><span class="mi">15</span><span class="p">,</span> <span class="mi">20</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">gamma</span>                   <span class="c1"># -w4  + h4/gamma &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">23</span><span class="p">,</span> <span class="p">[</span><span class="mi">15</span><span class="p">,</span> <span class="mi">20</span><span class="p">]]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="n">gamma</span>                       <span class="c1">#  w4 - gamma * h4 &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">24</span><span class="p">,</span> <span class="p">[</span><span class="mi">16</span><span class="p">,</span> <span class="mi">21</span><span class="p">]]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">gamma</span>                   <span class="c1"># -w5 + h5/gamma &lt;= 0</span>
    <span class="n">G</span><span class="p">[</span><span class="mi">25</span><span class="p">,</span> <span class="p">[</span><span class="mi">16</span><span class="p">,</span> <span class="mi">21</span><span class="p">]]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="o">-</span><span class="n">gamma</span>                       <span class="c1">#  w5 - gamma * h5 &lt;= 0.0</span>

    <span class="c1"># solve and return W, H, x, y, w, h</span>
    <span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">cpl</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">F</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">)</span>
    <span class="k">return</span>  <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">1</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">2</span><span class="p">:</span><span class="mi">7</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">7</span><span class="p">:</span><span class="mi">12</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">12</span><span class="p">:</span><span class="mi">17</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][</span><span class="mi">17</span><span class="p">:]</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">figure</span><span class="p">(</span><span class="n">facecolor</span><span class="o">=</span><span class="s1">&#39;w&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">subplot</span><span class="p">(</span><span class="mi">221</span><span class="p">)</span>
<span class="n">Amin</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">100.</span><span class="p">,</span> <span class="mf">100.</span><span class="p">,</span> <span class="mf">100.</span><span class="p">,</span> <span class="mf">100.</span><span class="p">,</span> <span class="mf">100.</span><span class="p">])</span>
<span class="n">W</span><span class="p">,</span> <span class="n">H</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">h</span> <span class="o">=</span>  <span class="n">floorplan</span><span class="p">(</span><span class="n">Amin</span><span class="p">)</span>
<span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">):</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">([</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span>
               <span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s1">&#39;#D0D0D0&#39;</span><span class="p">)</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="s2">&quot;</span><span class="si">%d</span><span class="s2">&quot;</span> <span class="o">%</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xticks</span><span class="p">([])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([])</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">subplot</span><span class="p">(</span><span class="mi">222</span><span class="p">)</span>
<span class="n">Amin</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">20.</span><span class="p">,</span> <span class="mf">50.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">,</span> <span class="mf">150.</span><span class="p">,</span> <span class="mf">200.</span><span class="p">])</span>
<span class="n">W</span><span class="p">,</span> <span class="n">H</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">h</span> <span class="o">=</span>  <span class="n">floorplan</span><span class="p">(</span><span class="n">Amin</span><span class="p">)</span>
<span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">):</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">([</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span>
               <span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span> <span class="s1">&#39;facecolor = #D0D0D0&#39;</span><span class="p">)</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="s2">&quot;</span><span class="si">%d</span><span class="s2">&quot;</span> <span class="o">%</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xticks</span><span class="p">([])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([])</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">subplot</span><span class="p">(</span><span class="mi">223</span><span class="p">)</span>
<span class="n">Amin</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">180.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">,</span> <span class="mf">80.</span><span class="p">])</span>
<span class="n">W</span><span class="p">,</span> <span class="n">H</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">h</span> <span class="o">=</span>  <span class="n">floorplan</span><span class="p">(</span><span class="n">Amin</span><span class="p">)</span>
<span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">):</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">([</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span>
               <span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span> <span class="s1">&#39;facecolor = #D0D0D0&#39;</span><span class="p">)</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="s2">&quot;</span><span class="si">%d</span><span class="s2">&quot;</span> <span class="o">%</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xticks</span><span class="p">([])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([])</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">subplot</span><span class="p">(</span><span class="mi">224</span><span class="p">)</span>
<span class="n">Amin</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">20.</span><span class="p">,</span> <span class="mf">150.</span><span class="p">,</span> <span class="mf">20.</span><span class="p">,</span> <span class="mf">200.</span><span class="p">,</span> <span class="mf">110.</span><span class="p">])</span>
<span class="n">W</span><span class="p">,</span> <span class="n">H</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">h</span> <span class="o">=</span>  <span class="n">floorplan</span><span class="p">(</span><span class="n">Amin</span><span class="p">)</span>
<span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">):</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">([</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span>
               <span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]],</span> <span class="s1">&#39;facecolor = #D0D0D0&#39;</span><span class="p">)</span>
    <span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">y</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">+.</span><span class="mi">5</span><span class="o">*</span><span class="n">h</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="s2">&quot;</span><span class="si">%d</span><span class="s2">&quot;</span> <span class="o">%</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">26</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xticks</span><span class="p">([])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([])</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">show</span><span class="p">()</span>
</pre></div>
</div>
<a class="reference internal image-reference" href="_images/floorplan.png"><img alt="_images/floorplan.png" src="_images/floorplan.png" style="width: 600px;" /></a>
</dd>
</dl>
</div>
<div class="section" id="geometric-programming">
<span id="s-gp"></span><h2>Geometric Programming<a class="headerlink" href="#geometric-programming" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.solvers.gp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">gp</code><span class="sig-paren">(</span><em class="sig-param">K</em>, <em class="sig-param">F</em>, <em class="sig-param">g</em><span class="optional">[</span>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.gp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a geometric program in convex form</p>
<div class="math">
<p><img src="_images/math/6dd83f47897e8af1a287a2cb577906b4c142c166.png" alt="\newcommand{\lse}{\mathop{\mathbf{lse}}}
\begin{array}{ll}
\mbox{minimize}   &amp; f_0(x) = \lse(F_0x+g_0) \\
\mbox{subject to} &amp; f_i(x) = \lse(F_ix+g_i) \leq 0,
                    \quad i=1,\ldots,m \\
                  &amp; Gx \preceq h \\
                  &amp; Ax=b
\end{array}"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/dcab68360c480e6aaf0001fa1fb3f6451ba747f0.png" alt="\newcommand{\lse}{\mathop{\mathbf{lse}}}
\lse(u) = \log \sum_k \exp(u_k), \qquad
F = \left[ \begin{array}{cccc}
     F_0^T &amp; F_1^T &amp; \cdots &amp; F_m^T
    \end{array}\right]^T, \qquad
g = \left[ \begin{array}{cccc}
     g_0^T &amp; g_1^T &amp; \cdots &amp; g_m^T
    \end{array}\right]^T,"/></p>
</div><p>and the vector inequality denotes componentwise inequality.
<code class="docutils literal notranslate"><span class="pre">K</span></code> is a list of <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> + 1 positive integers with <code class="docutils literal notranslate"><span class="pre">K[i]</span></code>
equal to the number of rows in <img class="math" src="_images/math/d907a3c4e1257ec91ba2b8475cc048392650b648.png" alt="F_i"/>.  <code class="docutils literal notranslate"><span class="pre">F</span></code> is a dense or
sparse real matrix of size <code class="docutils literal notranslate"><span class="pre">(sum(K),</span> <span class="pre">n)</span></code>.
<code class="docutils literal notranslate"><span class="pre">g</span></code> is a dense real matrix with one column and the same number of
rows as <code class="docutils literal notranslate"><span class="pre">F</span></code>.
<code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are dense or sparse real matrices.  Their default
values are sparse matrices with zero rows.
<code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are dense real matrices with one column.  Their
default values are matrices of size (0, 1).</p>
<p><a class="reference internal" href="#cvxopt.solvers.gp" title="cvxopt.solvers.gp"><code class="xref py py-func docutils literal notranslate"><span class="pre">gp</span></code></a> returns a dictionary with keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>.  The possible values of the
<code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> key are:</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code></dt><dd><p>In this case the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> entry is the primal optimal solution,
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code> entries are the corresponding
slacks in the nonlinear and linear inequality constraints.  The
<code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> entries are the
optimal values of the dual variables associated with the nonlinear
and linear inequality constraints and the linear equality
constraints.  These values approximately satisfy</p>
<div class="math">
<p><img src="_images/math/95a6e48cc402e2e0cee2fe87d159320f12dcadfc.png" alt="\nabla f_0(x) + \sum_{k=1}^m z_{\mathrm{nl},k}
    \nabla f_k(x) + G^T z_\mathrm{l} + A^T y = 0,

f_k(x) + s_{\mathrm{nl},k} = 0, \quad k = 1,\ldots,m
\qquad Gx + s_\mathrm{l} = h, \qquad Ax = b,

s_\mathrm{nl}\succeq 0, \qquad s_\mathrm{l}\succeq 0, \qquad
z_\mathrm{nl} \succeq 0, \qquad z_\mathrm{l} \succeq 0,

s_\mathrm{nl}^T z_\mathrm{nl} + s_\mathrm{l}^T z_\mathrm{l} =0."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code></dt><dd><p>This indicates that the algorithm terminated before a solution was
found, due to numerical difficulties or because the maximum number
of iterations was reached.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'snl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'znl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>
contain the iterates when the algorithm terminated.</p>
</dd>
</dl>
<p>The other entries in the output dictionary describe the accuracy
of the solution, and are taken from the output of
<a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a>.</p>
<p><a class="reference internal" href="#cvxopt.solvers.gp" title="cvxopt.solvers.gp"><code class="xref py py-func docutils literal notranslate"><span class="pre">gp</span></code></a> requires that the problem is strictly primal and dual
feasible and that</p>
<div class="math">
<p><img src="_images/math/c72b037a60f8e81dc19add786e6d148794471f80.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank \left( \left[ \begin{array}{cccccc}
     \sum_{k=0}^m z_k \nabla^2 f_k(x) &amp; A^T &amp;
      \nabla f_1(x) &amp; \cdots \nabla f_m(x) &amp; G^T
      \end{array} \right] \right) = n,"/></p>
</div><p>for all <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and all positive <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>.</p>
</dd></dl>

<p>As an example, we solve the small GP of section 2.4 of the paper
<a class="reference external" href="http://www.stanford.edu/~boyd/gp_tutorial.html">A Tutorial on Geometric Programming</a>.
The  posynomial form of the problem is</p>
<div class="math">
<p><img src="_images/math/7faf4e55287d19aeb554d113cd37857aeb2700b4.png" alt="\begin{array}{ll}
\mbox{minimize}
    &amp; w^{-1} h^{-1} d^{-1} \\
\mbox{subject to}
    &amp; (2/A_\mathrm{wall}) hw + (2/A_\mathrm{wall})hd \leq 1  \\
    &amp;  (1/A_\mathrm{flr}) wd \leq 1 \\
    &amp;  \alpha wh^{-1} \leq 1 \\
    &amp;  (1/\beta) hw^{-1} \leq 1 \\
    &amp;  \gamma wd^{-1} \leq 1 \\
    &amp;   (1/\delta)dw^{-1} \leq 1
 \end{array}"/></p>
</div><p>with variables <img class="math" src="_images/math/4c120f773ab4e1c59ad2bd44aae969ce24dd190a.png" alt="h"/>, <img class="math" src="_images/math/cc87ee665749db882f94e0d3707eb23e39638650.png" alt="w"/>, <img class="math" src="_images/math/badad346f6fbe2e237af99bfbd9a93a4da53a3da.png" alt="d"/>.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">log</span><span class="p">,</span> <span class="n">exp</span><span class="p">,</span> <span class="n">solvers</span>

<span class="n">Aflr</span>  <span class="o">=</span> <span class="mf">1000.0</span>
<span class="n">Awall</span> <span class="o">=</span> <span class="mf">100.0</span>
<span class="n">alpha</span> <span class="o">=</span> <span class="mf">0.5</span>
<span class="n">beta</span>  <span class="o">=</span> <span class="mf">2.0</span>
<span class="n">gamma</span> <span class="o">=</span> <span class="mf">0.5</span>
<span class="n">delta</span> <span class="o">=</span> <span class="mf">2.0</span>

<span class="n">F</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[[</span><span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">],</span>
             <span class="p">[</span><span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span>  <span class="mf">1.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">1.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">],</span>
             <span class="p">[</span><span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">1.</span><span class="p">]])</span>
<span class="n">g</span> <span class="o">=</span> <span class="n">log</span><span class="p">(</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">,</span> <span class="mi">2</span><span class="o">/</span><span class="n">Awall</span><span class="p">,</span> <span class="mi">2</span><span class="o">/</span><span class="n">Awall</span><span class="p">,</span> <span class="mi">1</span><span class="o">/</span><span class="n">Aflr</span><span class="p">,</span> <span class="n">alpha</span><span class="p">,</span> <span class="mi">1</span><span class="o">/</span><span class="n">beta</span><span class="p">,</span> <span class="n">gamma</span><span class="p">,</span> <span class="mi">1</span><span class="o">/</span><span class="n">delta</span><span class="p">])</span> <span class="p">)</span>
<span class="n">K</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span>
<span class="n">h</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">d</span> <span class="o">=</span> <span class="n">exp</span><span class="p">(</span> <span class="n">solvers</span><span class="o">.</span><span class="n">gp</span><span class="p">(</span><span class="n">K</span><span class="p">,</span> <span class="n">F</span><span class="p">,</span> <span class="n">g</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span> <span class="p">)</span>
</pre></div>
</div>
</div>
<div class="section" id="exploiting-structure">
<span id="s-nlcp"></span><h2>Exploiting Structure<a class="headerlink" href="#exploiting-structure" title="Permalink to this headline">¶</a></h2>
<p>By default, the functions <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> do not exploit problem
structure.  Two mechanisms are provided for implementing customized solvers
that take advantage of problem structure.</p>
<dl>
<dt><strong>Providing a function for solving KKT equations</strong></dt><dd><p>The most expensive step of each iteration of
<a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> is the
solution of a set of linear equations (<em>KKT equations</em>) of the form</p>
<div class="math" id="equation-e-cp-kkt">
<p><span class="eqno">(2)<a class="headerlink" href="#equation-e-cp-kkt" title="Permalink to this equation">¶</a></span><img src="_images/math/7eac6332e16c5424a4b290d2b9f9445c5214a1d1.png" alt="\left[\begin{array}{ccc}
    H        &amp; A^T &amp; \tilde G^T \\
    A        &amp; 0   &amp; 0  \\
    \tilde G &amp; 0   &amp; -W^T W
\end{array}\right]
\left[\begin{array}{c} u_x \\ u_y \\ u_z \end{array}\right]
=
\left[\begin{array}{c} b_x \\ b_y \\ b_z \end{array}\right],"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/322793af4baec9f7ebaa53c4c21f4a468036799a.png" alt="H = \sum_{k=0}^m z_k \nabla^2f_k(x), \qquad
\tilde G = \left[\begin{array}{cccc}
\nabla f_1(x) &amp; \cdots &amp; \nabla f_m(x) &amp; G^T \end{array}\right]^T."/></p>
</div><p>The matrix <img class="math" src="_images/math/1fbee781f84569077719a167b64e12064360fac1.png" alt="W"/> depends on the current iterates and is defined as
follows.  Suppose</p>
<div class="math">
<p><img src="_images/math/61425e89ec518b2689e5063426419950648cd2dc.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
u = \left( u_\mathrm{nl}, \; u_\mathrm{l}, \; u_{\mathrm{q},0}, \;
    \ldots, \; u_{\mathrm{q},M-1}, \; \svec{(u_{\mathrm{s},0})}, \;
    \ldots, \; \svec{(u_{\mathrm{s},N-1})} \right), \qquad"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/4c8eef5c3334015a2ce256c6afde864dcac2b7ad.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\symm}{{\mbox{\bf S}}}
u_\mathrm{nl} \in \reals^m, \qquad
u_\mathrm{l} \in \reals^l, \qquad
u_{\mathrm{q},k} \in \reals^{r_k}, \quad k = 0, \ldots, M-1,
\qquad
u_{\mathrm{s},k} \in \symm^{t_k},  \quad k = 0, \ldots, N-1."/></p>
</div><p>Then <img class="math" src="_images/math/1fbee781f84569077719a167b64e12064360fac1.png" alt="W"/> is a block-diagonal matrix,</p>
<div class="math">
<p><img src="_images/math/21281aa0c6a6c01b835faeb9de4a5ba91527df33.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
Wu = \left( W_\mathrm{nl} u_\mathrm{nl}, \;
     W_\mathrm{l} u_\mathrm{l}, \;
     W_{\mathrm{q},0} u_{\mathrm{q},0}, \; \ldots, \;
     W_{\mathrm{q},M-1} u_{\mathrm{q},M-1},\;
     W_{\mathrm{s},0} \svec{(u_{\mathrm{s},0})}, \; \ldots, \;
     W_{\mathrm{s},N-1} \svec{(u_{\mathrm{s},N-1})} \right)"/></p>
</div><p>with the following diagonal blocks.</p>
<ul>
<li><p>The first block is a <em>positive diagonal scaling</em> with a vector
<img class="math" src="_images/math/1f2cf406b1224eb3a604895ac84524c6aed56983.png" alt="d_{\mathrm{nl}}"/>:</p>
<div class="math">
<p><img src="_images/math/487040712ec6e78e6ce843fdedb84752b97c2547.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
W_\mathrm{nl} = \diag(d_\mathrm{nl}), \qquad
W_\mathrm{nl}^{-1} = \diag(d_\mathrm{nl})^{-1}."/></p>
</div><p>This transformation is symmetric:</p>
<div class="math">
<p><img src="_images/math/62cd1c16ca3ef9e2b0d5696a6a49b6b5a6d19130.png" alt="W_\mathrm{nl}^T = W_\mathrm{nl}."/></p>
</div></li>
<li><p>The second block is a <em>positive diagonal scaling</em> with a vector
<img class="math" src="_images/math/0202eb241774e15b6d1398f17dd161778e602b90.png" alt="d_{\mathrm{l}}"/>:</p>
<div class="math">
<p><img src="_images/math/a133c9dd8091526f677cfcc502fbf773387d84bf.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
W_\mathrm{l} = \diag(d_\mathrm{l}), \qquad
W_\mathrm{l}^{-1} = \diag(d_\mathrm{l})^{-1}."/></p>
</div><p>This transformation is symmetric:</p>
<div class="math">
<p><img src="_images/math/172415a1aefbbb006e616ac35d880030890ad136.png" alt="W_\mathrm{l}^T = W_\mathrm{l}."/></p>
</div></li>
<li><p>The next <img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/> blocks are positive multiples of <em>hyperbolic
Householder transformations</em>:</p>
<div class="math">
<p><img src="_images/math/0fc13f815b495c77d502992ae392d16844c0950b.png" alt="W_{\mathrm{q},k} = \beta_k ( 2 v_k v_k^T - J), \qquad
W_{\mathrm{q},k}^{-1} = \frac{1}{\beta_k} ( 2 Jv_k v_k^T J - J),
\qquad k = 0,\ldots,M-1,"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/8fcff6b5a5c95afb39f5abaedac94b7086911410.png" alt="\beta_k &gt; 0, \qquad v_{k0} &gt; 0, \qquad v_k^T Jv_k = 1, \qquad
J = \left[\begin{array}{cc} 1 &amp; 0 \\ 0 &amp; -I \end{array}\right]."/></p>
</div><p>These transformations are also symmetric:</p>
<div class="math">
<p><img src="_images/math/294ea142766a27b4576f8c3240182c9220174aad.png" alt="W_{\mathrm{q},k}^T = W_{\mathrm{q},k}."/></p>
</div></li>
<li><p>The last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> blocks are <em>congruence transformations</em> with
nonsingular matrices:</p>
<div class="math">
<p><img src="_images/math/45ab4648d9d463e88b6a823609eaac81787d876f.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k} \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k^T u_{\mathrm{s},k} r_k)}, \qquad
W_{\mathrm{s},k}^{-1} \svec{(u_{\mathrm{s},k})} =
   \svec{(r_k^{-T} u_{\mathrm{s},k} r_k^{-1})}, \qquad
k = 0,\ldots,N-1."/></p>
</div><p>In  general, this operation is not symmetric, and</p>
<div class="math">
<p><img src="_images/math/e2f6bbba20da0d51564b1855eb2da3072d841441.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k}^T \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k u_{\mathrm{s},k} r_k^T)}, \qquad
\qquad
W_{\mathrm{s},k}^{-T} \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k^{-1} u_{\mathrm{s},k} r_k^{-T})}, \qquad
k = 0,\ldots,N-1."/></p>
</div></li>
</ul>
<p>It is often possible to exploit problem structure to solve
<a class="reference internal" href="#equation-e-cp-kkt">(2)</a> faster than by standard methods.  The last argument
<code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> of <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> allows the user to
supply a Python function
for solving the KKT equations.  This function will be called as
<code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(x,</span> <span class="pre">z,</span> <span class="pre">W)</span></code>.  The argument <code class="docutils literal notranslate"><span class="pre">x</span></code> is the point at
which the derivatives in the KKT matrix are evaluated.  <code class="docutils literal notranslate"><span class="pre">z</span></code> is a
positive vector of length it <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> + 1, containing the coefficients
in the 1,1 block <img class="math" src="_images/math/cb5de54f699cf4b3c7c1a3e87313d11d536c0d88.png" alt="H"/>.  <code class="docutils literal notranslate"><span class="pre">W</span></code> is a dictionary that contains the
parameters of the scaling:</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">W['dnl']</span></code> is the positive vector that defines the diagonal
scaling for the nonlinear inequalities.  <code class="docutils literal notranslate"><span class="pre">W['dnli']</span></code> is its
componentwise inverse.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">W['d']</span></code> is the positive vector that defines the diagonal
scaling for the componentwise linear inequalities.  <code class="docutils literal notranslate"><span class="pre">W['di']</span></code>
is its componentwise inverse.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">W['beta']</span></code> and <code class="docutils literal notranslate"><span class="pre">W['v']</span></code> are lists of length <img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/>
with the coefficients and vectors that define the hyperbolic
Householder transformations.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">W['r']</span></code> is a list of length <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> with the matrices that
define the the congruence transformations.  <code class="docutils literal notranslate"><span class="pre">W['rti']</span></code> is a
list of length <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> with the transposes of the inverses of the
matrices in <code class="docutils literal notranslate"><span class="pre">W['r']</span></code>.</p></li>
</ul>
<p>The function call <code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(x,</span> <span class="pre">z,</span> <span class="pre">W)</span></code> should return a
routine for solving the KKT system <a class="reference internal" href="#equation-e-cp-kkt">(2)</a> defined by <code class="docutils literal notranslate"><span class="pre">x</span></code>,
<code class="docutils literal notranslate"><span class="pre">z</span></code>, <code class="docutils literal notranslate"><span class="pre">W</span></code>.  It will be called as <code class="docutils literal notranslate"><span class="pre">f(bx,</span> <span class="pre">by,</span> <span class="pre">bz)</span></code>.
On entry, <code class="docutils literal notranslate"><span class="pre">bx</span></code>, <code class="docutils literal notranslate"><span class="pre">by</span></code>, <code class="docutils literal notranslate"><span class="pre">bz</span></code> contain the right-hand side.  On exit,
they should contain the solution of the KKT system, with the last
component scaled, i.e., on exit,</p>
<div class="math">
<p><img src="_images/math/aaf1e4f8649093b3b1a2a201c97238b5d922ff96.png" alt="b_x := u_x, \qquad b_y := u_y, \qquad b_z := W u_z."/></p>
</div><p>The role of the argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> in the function
<a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a> is similar, except that in
<a class="reference internal" href="#equation-e-cp-kkt">(2)</a>,</p>
<div class="math">
<p><img src="_images/math/21f2b425bff574fa56ee14ddbb7517747adb4266.png" alt="H = \sum_{k=0}^{m-1} z_k \nabla^2f_k(x), \qquad
\tilde G = \left[\begin{array}{cccc}
\nabla f_0(x) &amp; \cdots &amp; \nabla f_{m-1}(x) &amp; G^T \end{array}\right]^T."/></p>
</div></dd>
<dt><strong>Specifying constraints via Python functions</strong></dt><dd><p>In the default use of <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a>, the arguments
<code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are the
coefficient matrices in the constraints of <a class="reference internal" href="#equation-e-cp-kkt">(2)</a>.  It is also
possible to specify these matrices by providing Python functions that
evaluate the corresponding matrix-vector products and their adjoints.</p>
<ul>
<li><p>If the argument <code class="docutils literal notranslate"><span class="pre">G</span></code> of <code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code> is a Python function, then
<code class="docutils literal notranslate"><span class="pre">G(u,</span> <span class="pre">v[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></code> should
evaluates the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/582940bfca19aac437939d3e7b6be8c577797dad.png" alt="v := \alpha Gu + \beta v \quad
    (\mathrm{trans} = \mathrm{'N'}), \qquad
v := \alpha G^T u + \beta v \quad
   (\mathrm{trans} = \mathrm{'T'})."/></p>
</div></div></blockquote>
</li>
<li><p>Similarly, if the argument <code class="docutils literal notranslate"><span class="pre">A</span></code> is a Python function, then
<code class="docutils literal notranslate"><span class="pre">A(u,</span> <span class="pre">v[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></code> should
evaluate the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/b8c391eb9c602cc714b875704be76879e335e243.png" alt="v \alpha Au + \beta v \quad
    (\mathrm{trans} = \mathrm{'N'}), \qquad
v := \alpha A^T u + \beta v \quad
    (\mathrm{trans} = \mathrm{'T'})."/></p>
</div></div></blockquote>
</li>
<li><p>In a similar way, when the first argument <code class="docutils literal notranslate"><span class="pre">F</span></code> of
<a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> returns matrices of first
derivatives or second derivatives <code class="docutils literal notranslate"><span class="pre">Df</span></code>, <code class="docutils literal notranslate"><span class="pre">H</span></code>, these matrices can
be specified as Python functions.  If <code class="docutils literal notranslate"><span class="pre">Df</span></code> is a Python function,
then <code class="docutils literal notranslate"><span class="pre">Df(u,</span> <span class="pre">v[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></code> should
evaluate the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/d452b345239711d0be1016ccde4ddfea5930b072.png" alt="v := \alpha Df(x) u + \beta v \quad
    (\mathrm{trans} = \mathrm{'N'}), \qquad
v := \alpha Df(x)^T u + \beta v \quad
    (\mathrm{trans} = \mathrm{'T'})."/></p>
</div></div></blockquote>
<p>If <code class="docutils literal notranslate"><span class="pre">H</span></code> is a Python function, then <code class="docutils literal notranslate"><span class="pre">H(u,</span> <span class="pre">v[,</span> <span class="pre">alpha,</span> <span class="pre">beta])</span></code> should
evaluate the matrix-vector product</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/3fb48872eb2d412f7878dd8934dab8823ce6422b.png" alt="v := \alpha H u + \beta v."/></p>
</div></div></blockquote>
</li>
</ul>
<p>If <code class="docutils literal notranslate"><span class="pre">G</span></code>, <code class="docutils literal notranslate"><span class="pre">A</span></code>, <code class="docutils literal notranslate"><span class="pre">Df</span></code>, or <code class="docutils literal notranslate"><span class="pre">H</span></code> are Python functions, then the
argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> must also be provided.</p>
</dd>
</dl>
<p>As an example, we consider the unconstrained problem</p>
<div class="math">
<p><img src="_images/math/8871516499f79705d3818c3251aacd463f7c5146.png" alt="\begin{array}{ll}
\mbox{minimize} &amp; (1/2)\|Ax-b\|_2^2 - \sum_{i=1}^n \log(1-x_i^2)
\end{array}"/></p>
</div><p>where <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/> is an <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> by <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> matrix with <img class="math" src="_images/math/e9bc7da808d33a16a8347f27a519bd067186aa66.png" alt="m"/> less
than <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>.  The Hessian of the objective is diagonal plus a low-rank
term:</p>
<div class="math">
<p><img src="_images/math/2211f73518e89008db8e07b1bb8a7b8881d0263f.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
H = A^TA + \diag(d), \qquad d_i = \frac{2(1+x_i^2)}{(1-x_i^2)^2}."/></p>
</div><p>We can exploit this property when solving <a class="reference internal" href="#equation-e-cp-kkt">(2)</a> by applying
the matrix inversion lemma. We first solve</p>
<div class="math">
<p><img src="_images/math/04163b47432b93c2e42e10bab40066847581fc79.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
(A \diag(d)^{-1}A^T + I) v = (1/z_0) A \diag(d)^{-1}b_x, \qquad"/></p>
</div><p>and then obtain</p>
<div class="math">
<p><img src="_images/math/d33cbbeb57b535cc4b2562e25475f7afc74ae85b.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
u_x = \diag(d)^{-1}(b_x/z_0 - A^T v)."/></p>
</div><p>The following code follows this method.  It also uses BLAS functions
for matrix-matrix and matrix-vector products.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">mul</span><span class="p">,</span> <span class="n">div</span><span class="p">,</span> <span class="n">log</span><span class="p">,</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">base</span>

<span class="k">def</span> <span class="nf">l2ac</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Solves</span>

<span class="sd">        minimize  (1/2) * ||A*x-b||_2^2 - sum log (1-xi^2)</span>

<span class="sd">    assuming A is m x n with m &lt;&lt; n.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">x</span> <span class="o">=</span> <span class="kc">None</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="kc">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">x</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="k">return</span> <span class="mi">0</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
        <span class="k">if</span> <span class="nb">max</span><span class="p">(</span><span class="nb">abs</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">&gt;=</span> <span class="mf">1.0</span><span class="p">:</span>
            <span class="k">return</span> <span class="kc">None</span>
        <span class="c1"># r = A*x - b</span>
        <span class="n">r</span> <span class="o">=</span> <span class="o">-</span><span class="n">b</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">)</span>
        <span class="n">w</span> <span class="o">=</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span>
        <span class="n">f</span> <span class="o">=</span> <span class="mf">0.5</span> <span class="o">*</span> <span class="n">blas</span><span class="o">.</span><span class="n">nrm2</span><span class="p">(</span><span class="n">r</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span>  <span class="o">-</span> <span class="nb">sum</span><span class="p">(</span><span class="n">log</span><span class="p">(</span><span class="mi">1</span><span class="o">-</span><span class="n">w</span><span class="p">))</span>
        <span class="c1"># gradf = A&#39;*r + 2.0 * x ./ (1-w)</span>
        <span class="n">gradf</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mf">1.0</span> <span class="o">-</span> <span class="n">w</span><span class="p">)</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">gradf</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;T&#39;</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">2.0</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">z</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">gradf</span><span class="o">.</span><span class="n">T</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">def</span> <span class="nf">Hf</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">):</span>
               <span class="c1"># v := alpha * (A&#39;*A*u + 2*((1+w)./(1-w)).*u + beta *v</span>
               <span class="n">v</span> <span class="o">*=</span> <span class="n">beta</span>
               <span class="n">v</span> <span class="o">+=</span> <span class="mf">2.0</span> <span class="o">*</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">mul</span><span class="p">(</span><span class="n">div</span><span class="p">(</span><span class="mf">1.0</span><span class="o">+</span><span class="n">w</span><span class="p">,</span> <span class="p">(</span><span class="mf">1.0</span><span class="o">-</span><span class="n">w</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span><span class="p">),</span> <span class="n">u</span><span class="p">)</span>
               <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
               <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;T&#39;</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">f</span><span class="p">,</span> <span class="n">gradf</span><span class="o">.</span><span class="n">T</span><span class="p">,</span> <span class="n">Hf</span>


    <span class="c1"># Custom solver for the Newton system</span>
    <span class="c1">#</span>
    <span class="c1">#     z[0]*(A&#39;*A + D)*x = bx</span>
    <span class="c1">#</span>
    <span class="c1"># where D = 2 * (1+x.^2) ./ (1-x.^2).^2.  We apply the matrix inversion</span>
    <span class="c1"># lemma and solve this as</span>
    <span class="c1">#</span>
    <span class="c1">#     (A * D^-1 *A&#39; + I) * v = A * D^-1 * bx / z[0]</span>
    <span class="c1">#     D * x = bx / z[0] - A&#39;*v.</span>

    <span class="n">S</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">m</span><span class="p">))</span>
    <span class="n">v</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">Fkkt</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">z</span><span class="p">,</span> <span class="n">W</span><span class="p">):</span>
        <span class="n">ds</span> <span class="o">=</span> <span class="p">(</span><span class="mf">2.0</span> <span class="o">*</span> <span class="n">div</span><span class="p">(</span><span class="mi">1</span> <span class="o">+</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span> <span class="o">-</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span><span class="p">))</span><span class="o">**-</span><span class="mf">0.5</span>
        <span class="n">Asc</span> <span class="o">=</span> <span class="n">A</span> <span class="o">*</span> <span class="n">spdiag</span><span class="p">(</span><span class="n">ds</span><span class="p">)</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">syrk</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
        <span class="n">S</span><span class="p">[::</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="mf">1.0</span>
        <span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">S</span><span class="p">)</span>
        <span class="n">a</span> <span class="o">=</span> <span class="n">z</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
        <span class="k">def</span> <span class="nf">g</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>
            <span class="n">x</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span> <span class="o">/</span> <span class="n">a</span>
            <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
            <span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
            <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;T&#39;</span><span class="p">)</span>
            <span class="n">x</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">g</span>

    <span class="k">return</span> <span class="n">solvers</span><span class="o">.</span><span class="n">cp</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">Fkkt</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span>
</pre></div>
</div>
</div>
<div class="section" id="algorithm-parameters">
<span id="s-parameters2"></span><h2>Algorithm Parameters<a class="headerlink" href="#algorithm-parameters" title="Permalink to this headline">¶</a></h2>
<p>The following algorithm control parameters are accessible via the
dictionary <code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options</span></code>.  By default the dictionary
is empty and the default values of the parameters are used.</p>
<p>One can change the parameters in the default solvers by
adding entries with the following key values.</p>
<dl class="simple">
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'show_progress'</span></code></dt><dd><p><code class="xref py py-const docutils literal notranslate"><span class="pre">True</span></code> or <code class="xref py py-const docutils literal notranslate"><span class="pre">False</span></code>; turns the output to the screen on or
off (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">True</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'maxiters'</span></code></dt><dd><p>maximum number of iterations (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">100</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'abstol'</span></code></dt><dd><p>absolute accuracy (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-7</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'reltol'</span></code></dt><dd><p>relative accuracy (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-6</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'feastol'</span></code></dt><dd><p>tolerance for feasibility conditions (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-7</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'refinement'</span></code></dt><dd><p>number of iterative refinement steps when solving KKT equations
(default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1</span></code>).</p>
</dd>
</dl>
<p>For example the command</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s1">&#39;show_progress&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span>
</pre></div>
</div>
<p>turns off the screen output during calls to the solvers.  The tolerances
<code class="xref py py-const docutils literal notranslate"><span class="pre">abstol</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">reltol</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">feastol</span></code> have the
following meaning in <a class="reference internal" href="#cvxopt.solvers.cpl" title="cvxopt.solvers.cpl"><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code></a>.</p>
<p><code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code> returns with status <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code> if</p>
<div class="math">
<p><img src="_images/math/727233e1f841277ba9bce9859cd9fbbe664f1667.png" alt="\newcommand{\ones}{{\bf 1}}
\frac{\| c +  Df(x)^Tz_\mathrm{nl} + G^Tz_\mathrm{l} + A^T y \|_2 }
{\max\{ 1, \| c + Df(x_0)^T\ones + G^T\ones \|_2 \}}
\leq \epsilon_\mathrm{feas}, \qquad
\frac{\| ( f(x) + s_{\mathrm{nl}},  Gx + s_\mathrm{l} - h,
 Ax-b ) \|_2}
{\max\{1, \| ( f(x_0) + \ones,
Gx_0 + \ones-h, Ax_0-b) \|_2 \}} \leq \epsilon_\mathrm{feas}"/></p>
</div><p>where <img class="math" src="_images/math/ed7fb0260e58d3ca5851e823ff991dae4cde5671.png" alt="x_0"/> is the point returned by <code class="docutils literal notranslate"><span class="pre">F()</span></code>, and</p>
<div class="math">
<p><img src="_images/math/1e7e60bfda710d3db286c7b54852b9cb3e77c861.png" alt="\mathrm{gap} \leq \epsilon_\mathrm{abs}
\qquad \mbox{or} \qquad \left( c^Tx &lt; 0, \quad
\frac{\mathrm{gap}} {-c^Tx} \leq \epsilon_\mathrm{rel} \right)
\qquad \mbox{or} \qquad
\left( L(x,y,z) &gt; 0, \quad \frac{\mathrm{gap}}
{L(x,y,z)} \leq \epsilon_\mathrm{rel} \right)"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/627d2d6ebe12e40470cbb763687cffb52453abe1.png" alt="\mathrm{gap} =
\left[\begin{array}{c} s_\mathrm{nl} \\ s_\mathrm{l}
\end{array}\right]^T
\left[\begin{array}{c} z_\mathrm{nl} \\ z_\mathrm{l}
\end{array}\right],
\qquad
L(x,y,z) = c^Tx + z_\mathrm{nl}^T f(x) +
    z_\mathrm{l}^T (Gx-h) + y^T(Ax-b)."/></p>
</div><p>The functions <a class="reference internal" href="#cvxopt.solvers.cp" title="cvxopt.solvers.cp"><code class="xref py py-func docutils literal notranslate"><span class="pre">cp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.gp" title="cvxopt.solvers.gp"><code class="xref py py-func docutils literal notranslate"><span class="pre">gp</span></code></a> call <code class="xref py py-func docutils literal notranslate"><span class="pre">cpl</span></code> and hence use the
same stopping criteria (with <img class="math" src="_images/math/459f00b80184047c37413367f1bc32570987f2c1.png" alt="x_0 = 0"/> for <code class="xref py py-func docutils literal notranslate"><span class="pre">gp</span></code>).</p>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="modeling.html" class="btn btn-neutral float-right" title="Modeling" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="coneprog.html" class="btn btn-neutral float-left" title="Cone Programming" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; <a href="copyright.html">Copyright</a> 2004-2020, M.S. Andersen, J. Dahl, L. Vandenberghe
      <span class="lastupdated">
        Last updated on Apr 16, 2020.
      </span>

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
  
    <div class="footer">
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 3.0.1.
    </div>

</body>
</html>